You're not currently signed in. Sign in »

Provably Efficient Algorithms for Numerical and Combinatorial Problems (CS 598 EVS) Spring 2020

What Where
Instructor <a href="http://solomonik.cs.illinois.edu/"Edgar Solomonik
Time/place Tu/Th 3:30pm-4:45pm, (virtual, email or see piazza for link to zoom, previously 1131 Siebel Center)
Office Hours After class, Tu/Th 4:45-5:30 (virtual, stay in zoom after lecture)
Class URL https://relate.cs.illinois.edu/course/cs598evs-s20/
Web forum View Piazza »
Calendar View Calendar »

Bridging the theory and practice of algorithms requires going beyond computational complexity to more sophisticated models of computer architecture and algorithmic cost. This course covers multiple analytical techniques that quantify the efficacy of an algorithm: parallel scalability, memory traffic, interprocessor communication, and numerical stability. General representations of algorithms (dependency graphs, bilinear algorithms) will be introduced as well as techniques for communication lower bound analysis. The course will look at problems from a variety of application domains, ranging from sorting and graph algorithms to numerical solvers and optimization. Special focus will be given to tensor computations.

The learning objective of the course is to develop techniques for mathematical representation and analysis of algorithms. Focus will be on numerical algorithms for matrix and tensor computations, but miscellaneous problems and algorithmic models will be considered. Topics of consideration will incorporate student interest/presentations.

Students will be expected to give a presentation relevant to the course, which may involve a discussion/activity, as well as to complete some assignments The assignments are planned to be given as in-class activities, but can also be completed offline. The presentation will comprise 70% and assignments 30% of the overall grade.

Quizzes (in-class activities)

Quiz 1: Interest Survey »

Quiz 2: Computing the Maximum Ritz Value »

Quiz 3: Finding Minimum of Quadratic Function in a Subspace »

Quiz 4: Bilinear Algorithms »

Quiz 5: Bitonic Sort »

Quiz 6: Algebraic Graph Algorithms »

Quiz 7: Bilinear Algorithms for Convolution »

Quiz 8: Triangular Matrix Inversion with Poly-Logarithmic Depth »

Quiz 9: General Matrix Inversion with Poly-Logarithmic Depth »

Quiz 10: Cache-Oblivious Fast Fourier Transform »

Quiz 11: Approximate Algorithms for Convolution »

Quiz 12: High-Order SVD »

Quiz 13: Alternating Least Squares for CP Decomposition of Tensors »

Quiz 14: Tensor Network Evolution »

Quiz 15: Eigenvalue Computation for Kronecker-Product Matrices using Imaginary Time Evolution »

Quiz 16: Eigenvalue Computation for Kronecker-Product Matrices using DMRG »

Quiz 17: Accelerated Bellman-Ford »

Quiz 18: Neural Network Robustness Verification »

Quiz 19: Bayesian Matrix Factorization with Monte Carlo »

Quiz 20: Computing Layer Potentials using Quadrature by Expansion »

Course Outline

  • Background Numerical Analysis Tools
    • Lecture Notes 
        </li>
  <li data-jstree='{"icon": "fa fa-keyboard-o"}'>
    <a href="repo:demos/upload/01-background-numerics/Conjugate Gradient Parallel Tangents as Krylov Subspace Method.html">Demo: Conjugate Gradient Parallel Tangents as Krylov Subspace Method</a>
    <ul>
      <li data-jstree='{"icon": "fa fa-newspaper-o"}'>
        <a href="repo:demos/upload/01-background-numerics/Conjugate Gradient Parallel Tangents as Krylov Subspace Method.html">View on the web</a>
      </li>
      <li data-jstree='{"icon": "fa fa-terminal"}'>
        <a href="repo:demos/upload/01-background-numerics/Conjugate Gradient Parallel Tangents as Krylov Subspace Method.py">Download Python script</a>
      </li>
      <li data-jstree='{"icon": "fa fa-download"}'>
        <a href="repo:demos/upload/01-background-numerics/Conjugate Gradient Parallel Tangents as Krylov Subspace Method.ipynb">Download Jupyter notebook</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-keyboard-o"}'>
    <a href="repo:demos/upload/01-background-numerics/Krylov Subspace Methods for Extremal Eigenvalue Problems.html">Demo: Krylov Subspace Methods for Extremal Eigenvalue Problems</a>
    <ul>
      <li data-jstree='{"icon": "fa fa-newspaper-o"}'>
        <a href="repo:demos/upload/01-background-numerics/Krylov Subspace Methods for Extremal Eigenvalue Problems.html">View on the web</a>
      </li>
      <li data-jstree='{"icon": "fa fa-terminal"}'>
        <a href="repo:demos/upload/01-background-numerics/Krylov Subspace Methods for Extremal Eigenvalue Problems.py">Download Python script</a>
      </li>
      <li data-jstree='{"icon": "fa fa-download"}'>
        <a href="repo:demos/upload/01-background-numerics/Krylov Subspace Methods for Extremal Eigenvalue Problems.ipynb">Download Jupyter notebook</a>
      </li>
    </ul>
  </li>
</ul>

    • Algorithm Representation
      • Lecture Notes
        • Lecture notes write-in template 
          •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/02-lecture-unfilled-scribbles-1.pdf">Lecture 2 Live Scribbles 1</a>
      </li>
    </ul>
  </li>
</ul>

        • Parallelism in Algorithms
          • Lecture Notes
            • Lecture notes write-in template 
              •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/03-lecture-unfilled.pdf.pdf">Lecture 3 Live Scribbles 1</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/03-lecture-unfilled-2.pdf">Lecture 3 Live Scribbles 2</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/03-lecture-unfilled-3.pdf">Lecture 3 Live Scribbles 3</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/03-lecture-unfilled-4.pdf">Lecture 3 Live Scribbles 4</a>
      </li>
    </ul>
  </li>
</ul>

            • Communication Cost of Algorithms
              • Lecture Notes
                • Lecture notes write-in template 
                  •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-1.pdf">Lecture 4 Live Scribbles 1</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-2.pdf">Lecture 4 Live Scribbles 2</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-3.pdf">Lecture 4 Live Scribbles 3</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-4.pdf">Lecture 4 Live Scribbles 4</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-5.pdf">Lecture 4 Live Scribbles 5</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-lecture-unfilled-6.pdf">Lecture 4 Live Scribbles 6</a>
      </li>
    </ul>
  </li>
</ul>

                • Tensor Computations

Related Courses

CS 598 EVS: Communication Cost Analysis of Algorithms, Fall '16

CS 554: Parallel Numerical Algorithms, Fall '19

CS 450: Numerical Analysis, Fall '18

Related Texts

  • Applied Numerical Linear Algebra James Demmel, SIAM, 1997.
  • Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
  • Numerical Linear Algebra Lloyd Trefethen and David Bau, SIAM, 1997.
  • An Introduction to Parallel Algorithms Joseph JaJa, 1992.

Python Help

We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments.

Python Workshop Material

Numpy Help